import collections
import heapq
class Solution(object):
    def secondMinimum(self, n, edges, time, change):
        d = collections.defaultdict(set)
        p = [[- float('inf'),  - float('inf')] for _ in range(n)]
        p[0][1] = 0
        for u, v in edges:
            u -= 1
            v -= 1
            d[u].add(v)
            d[v].add(u)
        st = [0]
        dist = 0
        while st:
            dist += 1
            next_st = []
            for node in st:
                for v in d[node]:
                    if dist < - p[v][0] and dist != - p[v][1]:
                        heapq.heapreplace(p[v], -dist)
                        next_st.append(v)
            st = next_st
        dist = - p[n - 1][0]
        ans = 0
        for _ in range(dist):
            if (ans // change) % 2 == 1:
                ans = (ans // change + 1) * change + time
            else:
                ans += time
        return ans


        

                

        


data = Solution()
n = 5
edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]
time = 3
change = 5
print(data.secondMinimum(n, edges, time, change))